 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        //1.创建一个大根堆
        priority_queue<int> heap;

        //2.将所有石头全部放进这个堆里
        for (auto& x : stones) heap.push(x);

        //3.遍历整个堆，对所有石头作为比较
        while (heap.size() > 1)
        {
            int a = heap.top(); heap.pop();
            int b = heap.top(); heap.pop();
            if (a > b) heap.push(a - b);
        }

        return heap.size() ? heap.top() : 0;
    }
};

class KthLargest {
public:
    //创建一个大小为k的小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    int _k;

    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for (auto& x : nums)
        {
            heap.push(x);
            if (heap.size() > _k) heap.pop();
        }
    }

    int add(int val) {
        heap.push(val);
        if (heap.size() > _k) heap.pop();

        return heap.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

class Solution {
public:
    typedef pair<string, int> PSI;

    struct cmp
    {
        bool operator()(PSI& a, PSI& b)
        {
            if (a.second == b.second)//频次相同，按照大根堆进行排序
            {
                return a.first < b.first;
            }

            return a.second > b.second;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        //1.创建一个哈希表用于存储每个单词出现的次数
        unordered_map<string, int> hash;

        for (auto& word : words) hash[word]++;

        //2.创建一个大小为k的堆
        priority_queue<PSI, vector<PSI>, cmp> heap;

        //3.存储进小根堆
        for (auto psi : hash)
        {
            heap.push(psi);
            if (heap.size() > k) heap.pop();
        }

        //4.将这组数据提取出来
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }

        return ret;
    }
};